package mylib.dir;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * User: 1
 * Date: 17.07.12
 * Time: 23:49
 * To change this template use File | Settings | File Templates.
 */
public class MatrixUtils {

    public static long[][] power(long[][] a, long power, long modulo) {
        long[][] res = unity((long) a.length);
        while (power > 0) {
            if (power % 2 == 0) {
                res = mul(res, a, modulo);
            }
            power /= 2;
            a = mul(a, a, modulo);
        }
        return res;
    }

    public static int[][] power(int[][] a, long power, int modulo) {
        int[][] res = unity(a.length);
        while (power > 0) {
            if (power % 2 == 0) {
                res = mul(res, a, modulo);
            }
            power /= 2;
            a = mul(a, a, modulo);
        }
        return res;
    }

    public static void fill(int[][] a, int value) {
        for (int[] b : a)
            Arrays.fill(b, value);
    }

    public static void fill(long[][] a, long value) {
        for (long[] b : a)
            Arrays.fill(b, value);
    }

    public static void fill(double[][] a, double value) {
        for (double[] b : a)
            Arrays.fill(b, value);
    }

    public static int[][] unity(int n) {
        int[][] a = new int[n][n];
        for (int i = 0; i < n; ++i)
            a[i][i] = 1;
        return a;
    }

    public static long[][] unity(long n) {
        long[][] a = new long[(int) n][(int) n];
        for (int i = 0; i < n; ++i)
            a[i][i] = 1;
        return a;
    }

    public static double[][] mul(double[][] a, double[][] b) {
        double[][] c = new double[a.length][b[0].length];
        for (int i = 0; i < a.length; ++i)
            for (int j = 0; j < b[0].length; ++j) {
                double res = 0;
                for (int k = 0; k < a[0].length; ++k) {
                    res += a[i][k] * b[k][j];
                }
                c[i][j] = res;
            }
        return c;
    }

    public static int[][] mul(int[][] a, int[][] b, int modulo) {
        int[][] c = new int[a.length][b[0].length];
        for (int i = 0; i < a.length; ++i)
            for (int j = 0; j < b[0].length; ++j) {
                long res = 0;
                for (int k = 0; k < a[0].length; ++k) {
                    res = (res + (long) a[i][k] * b[k][j]) % modulo;
                }
                c[i][j] = (int) res;
            }
        return c;
    }

    public static long[][] mul(long[][] a, long[][] b, long modulo) {
        long[][] c = new long[a.length][b[0].length];
        for (int i = 0; i < a.length; ++i)
            for (int j = 0; j < b[0].length; ++j) {
                long res = 0;
                for (int k = 0; k < a[0].length; ++k) {
                    res = (res + a[i][k] * b[k][j]) % modulo;
                }
                c[i][j] = res;
            }
        return c;
    }

    public static int[][] mul(int[][] a, int[][] b) {
        int[][] c = new int[a.length][b[0].length];
        for (int i = 0; i < a.length; ++i)
            for (int j = 0; j < b[0].length; ++j) {
                int res = 0;
                for (int k = 0; k < a[0].length; ++k) {
                    res += a[i][k] * b[k][j];
                }
                c[i][j] = res;
            }
        return c;
    }

    public static long[][] mul(long[][] a, long[][] b) {
        long[][] c = new long[a.length][b[0].length];
        for (int i = 0; i < a.length; ++i)
            for (int j = 0; j < b[0].length; ++j) {
                long res = 0;
                for (int k = 0; k < a[0].length; ++k) {
                    res += a[i][k] * b[k][j];
                }
                c[i][j] = res;
            }
        return c;
    }

    public static void fill(boolean[][] matrix, boolean b) {
        for (boolean[] booleans : matrix)
            Arrays.fill(booleans, b);
    }
}
